package chujisuanfa;

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        return   val +
                "," +left +
                "," + right;
    }
}
public class Tree {
    public boolean isSymmetric(TreeNode root) {
        //非递归方法
        Queue<TreeNode> queue= new LinkedList<>(); //队列内可以有空元素
        if(root==null) return true;
        queue.add(root.left);
        queue.add(root.right);
        while(!queue.isEmpty()){
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            if(left==null&&right==null) continue;
            if (left==null||right==null||left.val!=right.val) return false;
            queue.add(left.left);
            queue.add(right.right);
            queue.add(left.right);
            queue.add(right.left);
        }
        return true;
    }
    public static List<List<Integer>> levelOrder(TreeNode root){
        if(root==null) return null;
        List<List<Integer>> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> listsub = new ArrayList<>();
            int num = queue.size();
            for (int i=0;i<num;++i){
                TreeNode node = queue.poll();
                if(node.left!=null) queue.add(node.left);
                if(node.right!=null) queue.add(node.right);
                listsub.add(node.val);
            }
            list.add(listsub);
        }
        return list;
    }


// 搜索树
    public TreeNode sortedArrayToBST(int[] nums) {
        int len =nums.length;
        return sortTree(nums,0,len-1);
    }

    public TreeNode sortTree(int[] nums,int low,int high){
        if(low>high) return null;
        TreeNode root = new TreeNode();
        if(low==high){
            root.val=nums[low];
            return root;
        }
        int midle = (high+low)/2;
        root.val = nums[midle];

        root.left=sortTree(nums,low,midle-1);
        root.right=sortTree(nums,midle+1,high);
        return root;
    }

    //找出路径结点和为给定值的路径
        List<List<Integer>> llist = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        public List<List<Integer>> pathSum(TreeNode root, int target) {
            dfs(root,target);
            return llist;
        }

        void dfs(TreeNode root,int target){
            if(root==null) return;
            list.add(root.val);
            int sum =0;
            for(Integer i :list) sum+=i;

            if(root.left==null&&root.right==null){
                if(sum==target){
                    List<Integer> l = new ArrayList<>();
                    for (Integer i: list) l.add(i);
                    llist.add(l);
                }
            }else{
                dfs(root.right,target);
                dfs(root.left,target);
            }
            list.remove(list.size()-1);

        }
    //找出路径结点和为给定值的路径

    //二叉搜索树转为双向链表
    static class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val,Node _left,Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }


    Stack<Node> stack = new Stack<>();
    public Node treeToDoublyList(Node root) {


            treeToDL(root,2);
            Node head, tail,pre,next, n;
            tail = stack.pop();
            pre = tail;

            while(!stack.isEmpty()){
                n = stack.peek();
                pre.left = n;
                n.right = pre;
                pre = stack.pop();
            }
            pre.left = tail;
            tail.right = pre;
            head = pre;

            return head;
    }
    public void treeToDL(Node root,int k){
            if(root==null) return;
            if(root.right!=null) treeToDL(root.right,k);
            System.out.println(root.val==k);
            treeToDL(root.left,k);
    }
    //二叉搜索树转为双向链表

    //求公共祖先二叉搜索树
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==p) return p;
        if(root==q) return q;
        if(root.left!=null&&isAll(root.left,p,q)) return lowestCommonAncestor(root.left,p,q);
        if(root.right!=null&&isAll(root.right,p,q)) return lowestCommonAncestor(root.right,p,q);
        return root;
    }

    public boolean isAll(TreeNode root,TreeNode p, TreeNode q){
        //这个树是否包含这两个根节点
        boolean l=false,r=false;
        TreeNode P=root,Q=root;
        if(root==p) l=true;
        if(root==q) r=true;
        while(P!=null&&P!=p){
            if(P.val>p.val) P = P.left;
            else P=P.right;
        }
        if (P!=null) l = true;
        while(Q!=null&&Q!=q){
            if(Q.val>q.val) Q = Q.left;
            else Q=Q.right;
        }
        if(Q!=null) r = true;
        return r&&l;
    }
    //求公共祖先二叉搜索树

    //求公共祖先二叉树
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if(root==p) return p;
        if(root==q) return q;
        if(root.left!=null&&isExect(root.left,p)&&isExect(root.left,q)) return lowestCommonAncestor(root.left,p,q);
        if(root.right!=null&&isExect(root.right,p)&&isExect(root.right,q)) return lowestCommonAncestor(root.right,p,q);
        return root;
    }
    public boolean isExect(TreeNode root,TreeNode p){
        //这个树是否包含这个节点
        if(root==null) return false;
        TreeNode P=root;
        if(root==p) return true;
        return isExect(root.left,p)||isExect(root.right,p);
    }
    //求公共祖先二叉树

    // 由遍历得二叉树
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        if(preorder.length==0) return null;
        TreeNode head =new TreeNode(preorder[0]);
        if(preorder.length==1) return head;
        //划分左右子树
        int i = 0;
        while(inorder[i]!=preorder[0]) i++;
        int[] lpre=new int[i],lin=new int[i],rpre=new int[preorder.length-i-1],rin=new int[preorder.length-i-1];

        for(int n = 0;n<i;++n) {lpre[n]=preorder[n+1];lin[n]=inorder[n];}
        for(int n = rpre.length-1,k=preorder.length-1;n>=0;--n,--k) {rpre[n]=preorder[k];rin[n]=inorder[k];}

        head.left = buildTree(lpre,lin);
        head.right = buildTree(rpre,rin);

        return head;
    }
    // 由遍历得二叉树


    //序列化与反序列化
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
//        Queue<TreeNode> queue =new ArrayDeque<>();//会报空指针异常
        Queue<TreeNode> queue =new LinkedList<>();//不会报空指针异常，队列内可以有空元素，debug看源码可以知道原因

        if(root==null) return sb.toString();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node==null) sb.append("f");
            else sb.append(node.val);
            sb.append(',');
            if(node!=null){
                queue.add(node.left);
                queue.add(node.right);
            }
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {

        if (data.length()==0) return null;
        String[] str = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(str[0]));// 字符串转数字
        Queue<TreeNode> queue =new LinkedList<>();
        queue.add(root);
        int i =1;
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if (i<str.length&&!str[i].equals("f")){
                node.left=new TreeNode(Integer.parseInt(str[i]));
                queue.add(node.left);
            }
            i++;
            if (i<str.length&&!str[i].equals("f")){
                node.right=new TreeNode(Integer.parseInt(str[i]));
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }


    public static void main(String[] args) {
//        TreeNode root1 = new TreeNode(5,new TreeNode(2,new TreeNode(1,null,null),
//                                                              new TreeNode(4,null,null)),
//                                           new TreeNode(8,new TreeNode(7,null,null),null));
//
//        Node node = new Node(4, new Node(2,
//                                                    new Node(1,null,null),
//                                                    new Node(3,null,null)),
//                                     new Node(5,null,null));
//
        Tree t = new Tree();
        TreeNode root = new TreeNode(11,new TreeNode(22,null,null),new TreeNode(3,new TreeNode(4,null,null),null));

        System.out.println(t.deserialize("1,2,3,f,f,4,f,f,f"));
    }

}
